package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC449 {
    public long startExecuteTime = System.currentTimeMillis();


    public class Codec {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            Deque<TreeNode> queue = new LinkedList<>();
            queue.offerLast(root);
            StringBuilder serializedStr = new StringBuilder();
            boolean lastLayerAllNull = false;

            while (!queue.isEmpty()) {
                if (lastLayerAllNull) break;
                int size = queue.size();
                lastLayerAllNull = true;
                for (int i = 0; i < size; i++) {
                    TreeNode cur = queue.pollFirst();
                    if (null == cur) serializedStr.append("null").append(",");
                    else {
                        serializedStr.append(cur.val).append(",");
                        queue.offerLast(cur.left);
                        queue.offerLast(cur.right);
                        if (null != cur.left) lastLayerAllNull = false;
                        if (null != cur.right) lastLayerAllNull = false;
                    }
                }
            }

            return serializedStr.length() <= 0 ? "" : serializedStr.delete(serializedStr.length() - 1, serializedStr.length()).toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (null == data || data.length() <= 0) return null;
            if (data.startsWith("[")) data = data.substring(1, data.length() - 1);
            List<String> levelList = Arrays.asList(data.split(","));

            if (levelList == null || levelList.isEmpty() || levelList.get(0).equals("null")) {
                return null;
            }

            TreeNode root = new TreeNode(Integer.parseInt(levelList.get(0)));
            Deque<TreeNode> preLayer = new LinkedList<>();
            Deque<TreeNode> curLayer = new LinkedList<>();
            int curLayerSize = 2;

            TreeNode curNode;
            preLayer.addLast(root);

            int currentIdx = 1;
            int len = levelList.size();
            while (currentIdx < len) {
                curLayerSize = preLayer.size() * 2;
                TreeNode father = preLayer.pollFirst();
                int nextFatherFlag = 0;
                for (int i = 0; i < curLayerSize && currentIdx + i < len; i++) {
                    String curNodeVal = levelList.get(currentIdx + i);
                    if ("null".equals(curNodeVal)) curNode = null;
                    else curNode = new TreeNode(Integer.parseInt(curNodeVal));

                    if (i % 2 == 0) father.left = curNode;
                    else father.right = curNode;

                    if (null != curNode) curLayer.addLast(curNode);
                    if (++nextFatherFlag > 1) {
                        nextFatherFlag = 0;
                        father = preLayer.pollFirst();
                    }
                }

                preLayer = curLayer;
                curLayer = new LinkedList<>();
                currentIdx += curLayerSize;
            }

            return root;
        }
    }

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

    public void run() {
        Codec ser = new Codec();
        Codec deser = new Codec();
        TreeNode root = deser.deserialize("[3,1,4,null,2,null,null]");
        System.out.println(ser.serialize(root));
    }

    public static void main(String[] args) throws Exception {
        LC449 an = new LC449();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
